package other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 并查集
 */
public class UnionFindSet {

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet();
        int[] trance = new int[4];
        List<String> list = new ArrayList<>();
        list.add("0-1");
        list.add("0-2");
        list.add("0-3");
        list.add("1-2");
        list.add("1-3");
        list.add("2-3");

        for (int i = 0; i < trance.length; i++) {
            trance[i] = -1;
        }

        for (String s : list) {
            System.out.println(Arrays.toString(trance));
            String[] split = s.split("-");
            int find1 = unionFindSet.find(Integer.parseInt(split[0]), trance);
            int find2 = unionFindSet.find(Integer.parseInt(split[1]), trance);
            if (find1 != find2) {
                unionFindSet.union(find1, find2, trance);
            }
        }
    }

    public int find(int x, int[] trance) {
        if (trance[x] < 0)
            return x;
        else
            return find(trance[x], trance);
    }

    public void union(int root1, int root2, int[] trance) {
        trance[root1] = root2;//将root1作为root2的新树根
    }
}
